package com.jojo.elementary.day10_tree;

import com.jojo.elementary.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 94、二叉树的中序遍历
 *
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 *
 * 示例 1：
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 *
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：root = [1]
 * 输出：[1]
 *
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class TreeMidErgodic {

    /** myCode 递归 */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> left = new ArrayList<>();
        List<Integer> right;
        if (root == null){
            return left;
        }
        left = inorderTraversal(root.left);
        left.add(root.val);
        right = inorderTraversal(root.right);
        left.addAll(right);
        return left;
    }

    /** myCode 迭代 */
    public List<Integer> inorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty() || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else {
                TreeNode pop = stack.pop();
                list.add(pop.val);
                root = pop.right;
            }
        }
        return list;
    }

    /** myCode Morris遍历 */
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode p1 = root,p2;
        while(p1 != null){
            p2 = p1.left;
            if (p2 != null){
                while (p2.right != null && p2.right != p1){
                    p2 = p2.right;
                }
                if (p2.right == null){
                    p2.right = p1;
                    p1 = p1.left;
                }else {
                    p2.right = null;
                    list.add(p1.val);
                    p1 = p1.right;
                }
            }else {
                list.add(p1.val);
                p1 = p1.right;
            }
        }
        return list;
    }
}
